Any modern digital map (or mathematical graph, as they are sometimes known) of a road network, in its simplest form, is effectively a database consisting of a plurality of tables defining firstly nodes (which can be considered as points or zero-dimensional objects) most commonly representative of road intersections, and secondly lines between those nodes representing the roads between those intersections. In more detailed digital maps, lines may be divided into segments defined by a start node and end node, which may be the same in the case of a segment of zero length, but are more commonly separate. Nodes may be considered real or “valid” for the purposes of this application when they represent a road intersection at which a minimum of 3 lines or segments intersect, whereas “artificial” or “avoidable” nodes are those which are provided as anchors for segments not being defined at one or both ends by a real node. These artificial nodes are useful in digital maps to provide, among other things, shape information for a particular stretch of road or a means of identifying the position along a road at which some characteristic of that road changes, e.g. a speed limit.
In practically all modern digital maps, nodes and segments (and/or lines) are further defined by various properties or attributes which are again represented by data in the tables of the database. Each node will typically have latitude and longitude coordinates to define its real-world position. The complete “graph” of the road network is described by millions of nodes and segments to cover an area of spanning one or more countries, or part thereof.
In the context of devising a means of efficiently referencing or describing a location (i.e. a path through a road network), it is not only highly inefficient simply to provide an ordered list of all nodes (and/or segments, and optionally their attributes) within the digital map which form part of the location, but such a referencing method would necessitate that exactly the same digital map was used during any de-referencing which later occurred, for example in a mobile device to which the location reference was transmitted, because nodes, segments, lines and their attributes are practically only ever uniquely defined in a particular version of a map created by a particular map vendor. Even fundamental attributes such as longitude and latitude for a particular node might differ between different digital maps.
One particular attribute often provided in digital maps is a Traffic Message Channel (TMC) location table reference. TMC is a technology for delivering traffic and travel information to vehicle users, and more particularly to navigation systems (either portable or integrated) present within those vehicles and which include some form of digital map. A TMC message consists of an event code (which need not be traffic-specific, although these are most common) and a location code, often consisting of an ordered list of location references by means of which the location of the traffic event can be determined in the digital map and thus represented graphically on the screen of the navigation system. A number of pre-defined nodes in most commercially available digital maps are assigned a TMC location reference which is determined with reference to a limited location table. The location table consists of 216 (65536) location references corresponding to a similar number of physical or real world locations, usually road intersections, also identifiable in the digital map.
Although TMC messages are very efficient in that they can be as short as 37 bits in length and therefore do not impinge significantly on available bandwidth for broadcast data, only a fixed number of location references are available, and therefore typically only motorways and major highways (or intersections thereon) in each country offering TMC can be referenced. There are various other disadvantages of TMC location references. For instance, TMC location tables are                often maintained through a public authority or National Government,        prone to change between update cycles, which are traditionally quite long,        non-existent, or available only commercially, in some markets.        
Of course, decoding a TMC location reference is intrinsically simple in that a simple queries can be performed in the digital map database for each TMC location code resulting in immediate identification of the relevant correct nodes and segments (each map provider will include TMC location codes as part of the map production process ensuring precision), and thus the location can be immediately resolved. However, as it is becoming possible to identify traffic build up on secondary and urban roads using GSM and GPS probe data (e.g. vehicles users increasingly possess either a mobile phone or a connected satellite navigation devices useful as probes), TMC location codes are simply inadequate as far resolution is concerned.
One attempt to overcome some of the limitations of TMC location references or map-specific references is the Dynamic Location Referencing project, also known as AGORA-C (in the process of standardization under no. ISO 17572-1, 2, and 3). Although a complete description of the AGORA-C location referencing approach is beyond the scope of this application, the fundamentals of the approach are that a location reference can be completely specified by a set of location points, specified by coordinate pairs of latitude and longitude and ordered in a list, each point complying with various rules but most importantly being consecutive in terms of the location being referenced and the previous point in the list, i.e. successive points form a next-point-relationship. As with other location referencing systems, each point is provided with a number of attributes which assist in better defining that point, but specific to the AGORA-C method is the identification of each point as one of a location point, an intersection point, a routing point, or some combination of these three. Each point along the location at which the road section signature changes is represented by an intersection point, so locations being paths over a road network and which pass through intersections without any road section signature change need not be referenced by an intersection point. For example, if a location includes a section of motorway which includes junctions that are not relevant as far as the location is concerned, then there is no need to include intersection points for such junctions. One of the earlier steps in the AGORA-C encoding method is the determination of all intervening intersection points between a first and a last intersection point along the location at which a change of road section signature occurs.
All these points are added to a table of points ultimately forming part of the AGORA-C location reference. Within this table, at least two routing points will also have been identified, again according to certain rules. Routing points are provided where an intersection points alone are insufficient to unambiguously determine the correct location in the decoder, and are either added as separate points, or where a required routing point coincides with existing intersection point, a simple attribute change on the latter is effected.
Although this referencing approach is comprehensive in that it is possible to accurately and repeatably encode and decode any location existing within a geographical information system, it is believed that that the system is excessive and possibly redundant in certain aspects, and a more efficient encoding and decoding system is possible. For instance, although the referencing method is independent of any pre-compilation work and is map-independent, the average AGORA-C message size is significantly higher than 30 bytes per location reference. In terms of the devices which might commonly decode location references, such as personal navigation devices, PDAs, mobiles, or in-car integrated navigation systems, it is desirable that the received message be as short as possible to enable rapid decoding and ultimate resolution of the location represented thereby.
In the Applicant's application WO 2010/000707 A1 filed on 29 Jun. 2009 entitled “An Efficient Location Referencing Method”, the contents of which are hereby incorporated by reference, a technique is described for producing a machine-readable representation of a location in a manner which not only is considered optimised as far as overall byte length is concerned, but which is also considered as being map-agnostic.
In another application filed by the Applicant on 29 Jun. 2009 entitled “A Method of Resolving a Location from Encoded Data Representative thereof”, and published as WO 2010/000706 A1, a method of resolving a location is described. The contents of WO '706 is hereby incorporated by reference. The location is represented by structured data, typically a packet of binary data resulting from the encoding of an ordered list of location reference points representative of that location according to a physical data format specification using techniques described in WO '707. The method described is advantageous in being both economical in terms of required processing, and also achieving high success rates in terms of re-creating the correct location despite the relative brevity of received data regardless of the digital map used. In this regard, the method can be considered as map-agnostic, but the manner in which the decoding occurs, as opposed to the resolving of decoded data into a location, will inevitably be dependent on the predetermined format chosen.
While the encoding and decoding techniques described in WO '707 and WO '706 may solve many of the problems described above with previously known techniques, and have been found to facilitate resolution of locations in a second digital map using data describing the locations which has been encoded from a first digital map, the Applicant has realised that there remains scope for further refinement and improvement of these methods in relation to identifying the location in the second digital map when more than one possibility exists for a node and/or line or segment forming part of the location in the second digital map.
In accordance with the techniques described in WO '706, an ordered list of location reference points is used to resolve a location. The ordered list of reference points are representative of nodes in a first digital map, and are associated with information or attributes representative of properties of at least one specific line or segment in the first digital map emanating from or incident at the node. In accordance with the methods of WO '706, at least one candidate node in a second digital map is identified for each location reference point. For example, this may be a node identified as being a reasonable match due to its position. In addition at least one candidate line or segment in the second digital map emanating from or incident at the candidate node is identified. A route search is carried out in the second digital map between candidate nodes or candidate lines or segments for successive location reference points and those lines or segments forming part of the route determined extracted. This is repeated for each pair of consecutive location reference points.
In some situations more than one candidate node and/or more than one candidate line or segment in the second digital map may be identified for a given location reference point. The Applicant has realised that there remains a need for an improved method of resolving the location in the second digital map from the ordered list of location reference points in such situations.